package com.sakura.二叉树;

import java.util.ArrayList;
import java.util.List;

public class Code257_二叉树的所有路径 {


    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new Code257_二叉树的所有路径().new TreeNode(1);
        TreeNode node2 = new Code257_二叉树的所有路径().new TreeNode(2);
        TreeNode node3 = new Code257_二叉树的所有路径().new TreeNode(3);
        TreeNode node4 = new Code257_二叉树的所有路径().new TreeNode(4);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        List<String> strings = new Code257_二叉树的所有路径().binaryTreePaths(node1);
        for (String s : strings) {
            System.out.println(s);
        }
    }


    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new ArrayList<>();
        fn(root, "", ans);
        return ans;
    }
    // 递归三部曲
    // 1. 确定递归函数的参数和返回值
    //    参数：node 节点，ans: 路径总和  path:路径
    // 2. 确定终止条件
    //    node == null return
    // 3. 确定单层递归的逻辑
    public void fn(TreeNode node, String path, List<String> ans) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            ans.add(path + node.val);
        }
        fn(node.left, path + node.val + "->", ans);
        fn(node.right, path + node.val + "->", ans);
    }

}
